// 动态规划dp 时间 O(n) 空间 O(1)

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int pre1 = 1, pre2 = 2, num;
        for (int i = 3; i <= n; i++) {
            num = pre1 + pre2;
            pre1 = pre2;
            pre2 = num;
        }
        return num;
    }
};